home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 2: CDPD 1 / Almathera Ten on Ten - Disc 2: CDPD 1.iso / pd / 126-150 / 141 / sbprolog / c_source.zoo / data.rep < prev    next >
Text File  |  1988-01-03  |  8KB  |  187 lines
  1. Other system documentation:
  2.  
  3. Data Representations
  4. ====================
  5.  
  6. - Prolog Data Structures
  7.  
  8. We describe here how the SB-Prolog system represents its data structures and
  9. the macros that help the programmer manipulate them.  (The macros described
  10. here are found in sim/aux.h and types are found in sim/sim.h)
  11.  
  12. A Prolog data object (a term) is always represented beginning from a single
  13. tagged word (declared in C as type `word').  The tag is kept in the LOW-ORDER
  14. two bits of the word.  We will call such a tagged word a P-word (for Prolog
  15. data object word).  There are four tags:
  16.  
  17. 00: (FREE)
  18.  
  19. indicates this P-word is a ``reference'' or a pointer.  (All pointers are to
  20. four-byte boundaries, so the word itself is the address; no manipulation of
  21. the word is needed to calculate the effective address).  If the address is of
  22. this word itself, then this word represents a ``free'' variable.  If the
  23. address is to some other word, then the effective value of this word is
  24. obtained by looking at the P-word at that address.  The process of running a
  25. list of such references until a free variable or some other (see below)
  26. P-word is obtained is called ``dereferencing''.
  27.  
  28. There is a macro deref(op) which will dereference its argument (op).  This
  29. macro uses a temporary variable `top' of type `pw' (*word), so top must be
  30. declared.  It is most efficient to declare top a `register' variable.
  31.  
  32. 01: (CS or CS_TAG) 
  33.  
  34. indicates this P-word represents a term that is a constant or structure
  35. record.  For each constant symbol and structure symbol there is a record,
  36. called the PSC-entry for that symbol.  This record contains the arity of the
  37. symbol, a pointer to the name of the symbol, and the length of the name of
  38. the symbol.  (It may also contain other information depending on how the
  39. symbol is used.  See type psc_rec in sim/sim.h.)  Every time a constant or
  40. structure symbol is read in (or otherwise created), the same PSC record is
  41. found (by hashing) and that record is used in lieu of the character string.
  42. This is similar to the obj-list in Lisp implementations.  A P-word with a CS
  43. tag is a pointer to a pointer to the PSC-entry for the constant or structure
  44. represented.  If the symbol represented by a P-word is a constant, then
  45. (almost) all the CS P-words for that constant point to the same pointer to
  46. that constant's PSC-entry.  (For the interested, it is the pointer used in
  47. the hash chain.)  If the symbol is a structure symbol (i.e.  with arity Arity
  48. > 0), then this CS P-word represents a term with the structure symbol as its
  49. main structure symbol.  In this case the CS P-word points to Arity+1 words on
  50. the heap: the first word is a pointer to the PSC-entry for the structure
  51. symbol; the next Arity words are P-words for the Arity arguments of this
  52. term.
  53.  
  54. There are several macros which can be used to access these records. Given a
  55. P-word op, get_str_psc(op) returns a pointer to the PSC-entry for this
  56. record; get_str_arity(op) returns the arity of the symbol; get_str_length(op)
  57. returns the length of the name of the symbol.
  58.  
  59. 110: (INT)
  60.  
  61. indicates this P-word represents a 29-bit signed integer. The integer is
  62. obtained by (arithmetically) shifting the P-word three bits to the right.
  63.  
  64. 010: (FLOAT)
  65.  
  66. indicates this P-word represents a floating-point number.  The representation
  67. of floats is as follows: bits 0-2: tag (010); bits 3-7:  absolute value of
  68. exponent; bits 8-29: absolute value of mantissa; bit 30:  sign of exponent
  69. (1: negative); bit 31: sign of mantissa (1: negative).
  70.  
  71. The following macros (see sim/aux.h) allow playing with numeric P-words:
  72.  
  73.     intval(op)    returns the integer value represented by the P-word op
  74.             (op must be a integer P-word.)
  75.  
  76.     floatval(op)    returns the float value represented by the P-word op.
  77.             (op must be a float P-word.) (This is currently a
  78.              C function, not a macro.)
  79.  
  80.     numval(op)    returns the numeric value represented by the P-word
  81.             op (op must be an integer or float P-word.)
  82.  
  83.     makeint(val)     takes an integer val and returns the P-word to represent it.
  84.     
  85.     makefloat(val)    takes a float val and returns the P-word to represent it.
  86.             (This is currently a C function, not a macro.)
  87.  
  88.     isinteger(op)    true if op is an integer P-word.
  89.     
  90.     isfloat(op)    true if op is a float P-word.
  91.     
  92.     isnum(op)    true is op is a numeric P-word, i.e. integer or float.
  93.  
  94. 11: (LIST)
  95.  
  96. Since lists are so common in Prolog programs, a special representation is
  97. used for them to conserve space (and time). A P-word with a list tag is a
  98. pointer to a pair of words on the heap, that make up a cons node (or `.'
  99. record structure in Prolog terms). These two words are the P-words for the
  100. car (first) and cdr (second) fields of the cons (`.') record. One way to view
  101. it is that a LIST P-word is similar to a CS P-word that points to a structure
  102. record, except that the structure symbol is not represented in the record,
  103. but in the pointer to it. This is just an implementation device to try to
  104. save space. It has no semantic effect (and makes it harder to implement such
  105. predicates as `functor', `arg', etc. because they now have to special-case
  106. lists.)
  107.  
  108.  
  109. General macros for manipulating tags:
  110.  
  111. There are two general macros which turn off tag bits: untag(op) which sets
  112. the tag bits of op to 00, and untagged(op) which is a function that returns
  113. the untagged version of op and leaves op unchanged.  There are also several
  114. macros which can be used to test the type of a DEREFERENCED P-word:
  115.  
  116.     isatom(op) is true if op represents a symbolic constant (not integer).
  117.     isnonvar(op) is true if op is NOT a free variable.
  118.     isfree(op) is true if op IS a free variable.
  119.     isinteger(op) is true if op represents an integer
  120.     isconstr(op) is true if op is a constant or a structure-term
  121.     islist(op) is true if op represents a list
  122.     isnil(op) is true if op is the P-word that represents the constant [].
  123.  
  124. Switch on type of P-word:
  125.  
  126. Given a P-word, it is sometimes required to take different actions depending
  127. on the tag.  Since the P-word must first be dereferenced, this is not JUST a
  128. simple switch construct.  The skeleton below is the most efficient way (we
  129. have thus far found) to handle such a case:
  130.  
  131.     newlabel: switch (op & TAGMASK) {
  132.     case FREE:
  133.         nderef(op, newlabel);
  134.         { code to handle free variable }
  135.         break;
  136.     case CS:
  137.         { code to handle constant or structure }
  138.         break;
  139.     case NUM:
  140.         { code to handle number }
  141.         break;
  142.     case LIST:
  143.         { code to handle list }
  144.         break;
  145.     }
  146.  
  147. In this code op contains a P-word, newlabel is a label to branch back to if
  148. dereferencing is necessary. (nderef also requires that `top' be declared.)
  149.  
  150. General Unification:
  151.  
  152. There is a general unification routine called unify. It is passed two P-words
  153. and unifies them (NOT doing occur-check). It changes the global data
  154. structures, binding variables and trailing such bindings as necessary. It
  155. returns true if the terms unify and false if they do not. It is the
  156. responsibility of the caller to perform the Fail if unify returns false. So
  157. the call to unify usually occurs as:
  158.  
  159.     if (!unify(op1,op2)) {Fail0;}
  160.  
  161. Fail0 is a macro which sets the address of the next instruction to be that of
  162. a fail instruction.  Fail0 is used in builtins and requires the brackets.
  163. (There is also a Fail1 macro which directly changes the register version of
  164. the program counter and is used only in main.)
  165.  
  166. Registers:
  167.  
  168. The Prolog engine has a set of registers.  Parameters are passed to invoked
  169. procedures by putting the P-words of the N arguments in registers 1 - N.  The
  170. registers are kept in the C simulator in an array of words called reg.
  171. (Various machinations are done to allow fast access to this array; such as
  172. putting its address in a register variable and accessing by displacement.
  173. This is done only in the main routine.)  It should be noted that a register
  174. will never contain a free variable (which would be represented by a pointer
  175. to itself); it may contain any other form of P-word.  For writing builtins,
  176. the macro gregc(i) is provided which returns the P-word in register i.  A
  177. common sequence of instructions at the beginning of a builtin is:
  178.  
  179.     register word op1;
  180.     register pw top;
  181.     num int;
  182.  
  183.     op1 = gregc(1); /* P-word from register 1 into op1 */
  184.     deref(op1);    /* dereference that P-word */
  185.     num = numval(op1);    /* e.g., we know it must be a number, so get
  186.                     its value */
  187.